﻿#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
//给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，
//其余每个元素均出现两次。找出那个只出现了一次的元素。
//int singleNumber(vector<int>& nums) {
//    int num = 0;
//    for (auto v : nums)
//    {
//        num ^= v;
//    }
//    return num;
//}

//给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
//vector<vector<int>> generate(int numRows) {
//    vector<vector<int>> vv;
//    vv.resize(numRows);
//    for (int i = 0; i < numRows; i++)
//    {
//        vv[i].resize(i + 1);
//        vv[i][0] = vv[i][i] = 1;
//    }
//    for (int i = 0; i < numRows; i++)
//    {
//        for (int j = 0; j < i; j++)
//        {
//            if (vv[i][j] == 0)
//            {
//                vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
//            }
//        }
//    }
//    return vv;
//}

//给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，
//使每个元素 只出现一次 ，返回删除后数组的新长度。元素的相对顺序应该
//保持 一致 。然后返回 nums 中唯一元素的个数。
//思路一：迭代器连续删除
//int removeDuplicates(vector<int>& nums) {
//    auto it = nums.begin();
//    int size = nums.size();
//    for (int i = 0; i < size; i++)
//    {
//        while (i + 1 < nums.size() && nums[i] == nums[i + 1])
//        {
//            nums.erase(it + i + 1);
//        }
//    }
//    return nums.size();
//}
//思路二：快慢指针
//int removeDuplicates(vector<int>& nums) {
//    int slow = 0, fast = 1;
//    int size = nums.size();
//    while (fast < size)
//    {
//        if (nums[slow] == nums[fast])
//        {
//            fast++;
//        }
//        else
//        {
//            nums[++slow] = nums[fast];
//        }
//    }
//    return slow + 1;
//}


//给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。
// 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
//思路：先排序，如果两个相邻元素相同，则索引加2，如果不同，则把第一个元素加到vector里
//      随后索引加1，当退出时，如果vector只有一个元素，则把末尾的元素 加到vector里
//vector<int> singleNumber(vector<int>& nums) {
//    sort(nums.begin(), nums.end());
//    vector<int> ret;
//    int i = 0;
//    while (i < nums.size())
//    {
//        if (i + 1 < nums.size())
//        {
//            if (nums[i] == nums[i + 1])
//                i += 2;
//            else
//            {
//                ret.push_back(nums[i]);
//                i++;
//            }
//        }
//        else
//            break;
//    }
//    if (ret.size() == 1)
//        ret.push_back(nums[nums.size() - 1]);
//    return ret;
//}

//给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
//int MoreThanHalfNum_Solution(vector<int>& numbers) {
//    sort(numbers.begin(), numbers.end());
//    int size = numbers.size();
//    int ret = size / 2;
//    return numbers[ret];
//}

//给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合
//思路：按照dfs，将数字字符串的长度看成总层数，从0到字符串长度，分别看成对应层数
//      每层包含有cstr中的对应字符串，可以依次选择字符串中的一个字符
//      按照层数，每次选取这一层的一个字符加到字符串上，当走完最后一层时，
//      把已有的字符串加给vector<string>，并返回;

string cstr[10] = { "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };//数字与字符的对应关系
//digits是数字字符串 level表示层数 str是选取出元素组成的字符串 v存储已组好的字符串
void combine(string digits, int level, string str, vector<string>& v)
{
    //如果层数等于数字字符串的长度，则表示已经组好字符串
    if (level == digits.size())
    {
        v.push_back(str);
        return;
    }

    //将数字字符串的数字元素转换为整形
    int str_num = digits[level] - '0';
    
    //依次从对应字符串中选出一个字符，加到str上
    for (int i = 0; i < cstr[str_num].size(); i++)
    {
        //选出元素后，把元素加到str上，并让层数+1，在下一层再次选一个元素
        combine(digits, level + 1, str + cstr[str_num][i], v);
    }
}

vector<string> letterCombinations(string digits) {
    string str;
    vector<string> ret;
    //如果数字字符串为空，则返回空
    if (digits.size() == 0)
        return ret;
    combine(digits, 0, str, ret);
    return ret;
}

//给你一个整数数组 nums除某个元素仅出现一次外其余每个元素都恰出现三次 。
//请你找出并返回那个只出现了一次的元素。
int singleNumber(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<int> ret;
    int i = 0;
    while (i < nums.size())
    {
        if (i + 2 < nums.size())
        {
            if (nums[i] == nums[i + 1] && nums[i + 1] == nums[i + 2])
            {
                i += 3;
            }
            else
            {
                return nums[i];
            }
        }
        else
        {
            if (ret.size() == 0)
            {
                return nums[i];
            }
            else
                break;
        }
    }
    return ret[0];
}

int main()
{
    vector<int> v;
    v.push_back(2);
    v.push_back(2);
    v.push_back(3);
    v.push_back(2);
    singleNumber(v);
}
//int main()
//{
//    vector<int> v;
//    v.push_back(1);
//    v.push_back(2);
//    v.push_back(1);
//    v.push_back(3);
//    v.push_back(2);
//    v.push_back(5);
//    singleNumber(v);
//    return 0;
//}
